package com.canopys.study.open.test.algorithm.dynamic;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 22:47 2020/12/6
 * @Modified By:
 */
public class Money {
    public static int MIN_COUNT = -1;
    public static int MAX_SUM = 9;


    // 回溯法
    public static void money(int[] a, int n, int sum) {
        if (sum > MAX_SUM) {
            return;
        }
        if (sum == MAX_SUM) {
            if (MIN_COUNT == -1 || MIN_COUNT > n) {
                MIN_COUNT = n;
                return;
            }
        }

        for (int i = 0; i < a.length; i++) {
            if (MAX_SUM - a[i] >= 0) {
                money(a, n + 1, sum + a[i]);
            }
        }

    }

    public static void money2(int[] a, int max) {
        int[] states = new int[max + 1];
        for (int i = 0; i < max; i++) {
            states[i] = 0;
        }

        /*for (int i = 0; i < a.length; i++) {
            if (a[i] < max + 1) {
                states[a[i]] = 1;
            }
        }*/

        for (int i = 0; i < max + 1; i++) {
            for (int j = 0; j < a.length; j++) {
                if (i + a[j] <= max) {
                    if (states[i + a[j]] == 0) {
                        states[i + a[j]] = states[i] + 1;
                    }
                    states[i + a[j]] = Math.min(states[i + a[j]], states[i] + 1);
                }
            }
        }

        System.out.println(states);


    }

    public static void main(String[] args) {
        int[] a = new int[] {3, 1, 5};
        MAX_SUM = 10;
        money(a, 0, 0);
        System.out.println(MIN_COUNT);

        money2(a, MAX_SUM);
    }
}
